% This file was converted to LaTeX by Writer2LaTeX ver. 1.1.8
% see http://writer2latex.sourceforge.net for more info
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[T3,T1]{fontenc}
\usepackage[polish]{babel}
\let\lll\undefined
\usepackage[noenc]{tipa}
\usepackage{tipx}
\usepackage[geometry,weather,misc,clock]{ifsym}
\usepackage{pifont}
\usepackage{eurosym}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amssymb,amsfonts,textcomp}
\usepackage{array}
\usepackage{supertabular}
\usepackage{hhline}
\usepackage{graphicx}
\makeatletter
\newcommand\arraybslash{\let\\\@arraycr}
\makeatother
\setlength\tabcolsep{1mm}
\renewcommand\arraystretch{1.3}
\newcounter{Drawing}
\renewcommand\theDrawing{\arabic{Drawing}}
\newcounter{Wykres}
\renewcommand\theWykres{\arabic{Wykres}}
\title{}
\begin{document}
Uniwersytet Gdański

\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img001.svm}

\end{figure}
\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img002.svm}

\end{figure}
Wydział Matematyki, Fizyki i Informatyki


\bigskip


\bigskip


\bigskip


\bigskip

Gene Expression Programming

wraz z biblioteką programów.

Bartłomiej Kossakowski


\bigskip


\bigskip


\bigskip


\bigskip

Promotor:

prof. dr hab. Joanna Jędrzejowicz

\clearpage\section[Wstęp]{\selectlanguage{polish} Wstęp}
Nie będzie przesadą stwierdzenie, że inspiracje zjawiskami przyrodniczymi przy rozwiązywaniu problemów człowieka pojawiały się już u pierwszych przedstawicieli naszego gatunku. Od imitujących pazury dzikich zwierząt ostrzach używanych przez myśliwych, przez obserwacje lotu ptaków by samemu wzbić się w powietrze, do czasów nam współczesnych, wciąż spoglądamy na techniki wykorzystywane przez naturę. Zdaje się więc, że kwestią czasu było zainteresowanie się mechanizmami biologicznymi przez informatyków. Nie inaczej narodziły się idee stworzenia sztucznej inteligencji czy „sztucznego życia” w oparciu o programy komputerowe. Same algorytmy będące próbą połączenia teorii ewolucji z informatyką, są tworem stosunkowo młodym, badania nad nimi sięgają lat pięćdziesiątych dwudziestego wieku, przełom zaś nastąpił w połowie lat sześćdziesiątych. \ 

Jak przeczytać można w [4], podstawowymi uwarunkowaniami ewolucji są dobór naturalny (selekcja) oraz rozmnażanie płciowe (zapewnienie różnorodności), w uproszczeniu zaś proces można określić jako „walka o przetrwanie najlepiej przystosowanych” osobników. Czytając dalej, należy zaznaczyć, że w darwinowskiej teorii ewolucji zachodzące zmiany mają na celu odnajdowanie ulepszeń, nie zaś rozwiązania optymalnego.

Algorytm genetyczny stanowi rozszerzenie idei algorytmu ewolucyjnego poprzez uogólnienie go do tego stopnia, by był w stanie reprezentować strukturę każdego problemu ([4]). W każdym jednak przypadku, działanie opiera się na trzech podstawowych krokach:

\begin{itemize}
\item stworzeniu populacji początkowej
\item ocenie jakości osobników
\item stworzenie kolejnej populacji poprzez operacje genetyczne na osobnikach.
\end{itemize}
Osobniki populacji nazywane są chromosomami, składają się one z szeregu genów, które zaś przyjmować mogą skończoną liczbę wartości, nazywanych allelami. Zespół genów, składających się na osobnika nazywamy genotypem, zaś jego produkt, rozumiany jako zbiór cech organizmu powstały z interakcji genotypu ze środowiskiem, nazywany jest fenotypem.

W przypadku, gdy osobnik reprezentuje spójny program komputerowy, mechanizm ten nazywany jest programowaniem genetycznym. 

Ciekawe i nowatorskie podejście do algorytmów ewolucyjnych, Gene Expression Programming – Programowanie Ekspresji Genu, zaprezentowane zostało przez dr \textbf{Cândidę Ferreirę po raz pierwszy w pracy [1]. Ta właśnie technika, wraz z przykładem implementacji oraz przykładami zastosowania, jest przedmiotem tej pracy.}


\bigskip


\bigskip

\subsection[Ekspresja genu]{\selectlanguage{polish} Ekspresja genu}
„Gene expression” - czyli ekspresja genu - jest jednym z podstawowych procesów w makromolekularnych mechanizmach życiowych. W uproszczeniu, polega on na odczytaniu informacji zawartych w genie i przepisaniu ich na białka lub formy kwasów rybonukleinowych (RNA), stanowiące produkty procesu. Wykorzystywany jest przez wszystkie znane formy życia, zarówno eukarionty (organizmy zbudowane z komórek posiadających jądro komórkowe i chromosomy), prokarionty (mikroorganizmy niezawierające jądra komórkowego, np bakterie), jak i prawdopodobnie wirusy. Proces ten ilustruje rysunek 1.\footnote{The Medical News, http://www.news-medical.net/health/What-is-Gene-Expression.aspx, tłumaczenie własne}


\bigskip

Proces przebiega etapowo\footnote{W opisie pominięto etapy o niewielkiej istotności z punktu widzenia informatyki, takie jak transport czy degradacja RNA i białek \ }:

\begin{figure}
\centering
\begin{minipage}{9.636cm}
Rysunek \stepcounter{Drawing}{\theDrawing}: Struktura oraz ekspresja genu
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img003.jpg}
\end{minipage}
\end{figure}
\begin{itemize}
\item transkrypcja, czyli przepisywanie informacji zawartej w DNA na RNA, w wyniku której powstaje pre-mRNA (RNA zawierający sekwencje niekodujące, tzw introny, oraz części kodujące, tzw egzony)
\item obróbka post-transkrypcyjna, w wyniku której powstaje mRNA (RNA przenoszący informacje)
\item translacja białka, czyli ostateczne formowanie białka na podstawie informacji zawartych w kodzie genetycznym. 


\bigskip
\end{itemize}
Sekwencja mogąca ulec translacji w białko nazywana jest otwartą ramką odczytu (ORF – ang. Open Reading Frame). Pojęcie to jednak w kontekście GEP ma nieco inne znaczenie, które zostanie opisane poniżej.


\bigskip


\bigskip

\subsection[GEP a algorytmy genetyczne i programowanie genetyczne]{\selectlanguage{polish} GEP a algorytmy genetyczne i programowanie genetyczne}
Idea przyświecająca algorytmom ewolucyjnym polega na przeszukiwaniu przestrzeni rozwiązań w celu znalezienia najlepszego z nich. W tym celu wprowadza się pewną losowo wygenerowaną populację, na której wykonywane są operacje genetyczne. Populacja składa się z chromosomów, w których zakodowane są informacje. Z każdą iteracją pętli algorytmu, z puli „kandydatów na rozwiązania” - z pomocą funkcji przystosowania, oceniającej jakość fenotypu (rozwiązania przedstawianego przez chromosom) - wybierane są osobniki najlepiej rokujące, będące następnie „rodzicami” kolejnej populacji. 


\bigskip

GEP łączy elementy dwóch podstawowych podejść do obliczeń ewolucyjnych, mianowicie algorytmy genetyczne (GA - ang. genetic algorithms) oraz programowanie genetyczne (GP - ang. genetic programming). 

W algorytmach genetycznych w tradycyjnej formie, istotnym problemem implementacji jest kwestia kodowania informacji w chromosomie. Najczęściej spotykanym (niejako kanonicznym) podejściem jest użycie chromosomów w postaci wektorów zero-jedynkowych o jednakiej długości, w których genem nazywamy pojedynczy bit, choć nie jest to regułą. Operacje genetyczne są wtenczas wykonywane bezpośrednio na ciągu znaków, nie zachodzi potrzeba kontroli osobnika pod kontem spójności. Przykład operacji mutacji na typowym dla GA chromosomie przedstawiony jest poniżej 

[Warning: Draw object ignored]\ \ \ \ 01001101 \ \ \ \  01000101


\bigskip


\bigskip


\bigskip


\bigskip

Programowanie genetyczne z kolei, za swój cel stawia znalezienie programu rozwiązującego problem. Różnica względem klasycznego GA polega na formie chromosomów. Z racji specyfiki rozpatrywanych problemów, osobniki populacji reprezentują drzewo składni. Przechowywanie osobnika jest kwestią implementacji, jednak najpopularniejszym podejściem jest rzutowanie drzewa na ciąg operacji w notacji quasi-prefiksowej. Długość chromosomu oraz rodzaj elementów go tworzących nie jest więc z góry ustalona. Operacje genetyczne są w tym przypadku przeprowadzane na drzewie, które podatne jest na utratę spójności przy ingerowaniu bezpośrednio w ciąg znaków. Konieczne jest więc zagwarantowanie, że np. krzyżowane będą jedynie poddrzewa (przykład krzyżowania poddrzew przedstawiony jest na rysunku 2.). 

\begin{figure}
\centering
\begin{minipage}{9.419cm}
Rysunek \stepcounter{Drawing}{\theDrawing}: Przykład krzyżowania poddrzew stosowanego w programowaniu genetycznym. 
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img004.gif}
\end{minipage}
\end{figure}
Opisywanie w niniejszej pracy podejście łączy zalety GA i GP. Populacja składa się z ciągów znaków jednakowej długości, jednak reprezentujących drzewo parsowania. Operacje genetyczne dokonują się na wektorze przed zinterpretowaniem go jako drzewo. Pozwala to zapobiec wystąpieniu „błędnych protein”. 


\bigskip

\section[Opis algorytmu]{\selectlanguage{polish} Opis algorytmu}
\begin{figure}
\centering
\begin{minipage}{8.557cm}
Rysunek \stepcounter{Drawing}{\theDrawing}: Schemat blokowy algorytmu GEP
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img005.jpg}
\end{minipage}
\end{figure}
W rozdziale tym przedstawiony i omówiony zostanie algorytm GEP, jego przebieg, oraz szczegóły struktur jego podstawowych „aktorów”. Prezentuje on również metodę, którą realizowana jest ekspresja genów nim używanych.


\bigskip

\subsection[Przebieg algorytmu]{\selectlanguage{polish} Przebieg algorytmu}
Przebieg algorytmu przedstawia schemat na 3. Na jego początku, po wygenerowaniu losowej populacji początkowej, każdy z chromosomów tłumaczony jest na drzewo składni, reprezentujące program. Każdy z nich oceniany jest przez funkcję przystosowania. Następnie, jeśli osiągnięty został wynik satysfakcjonujący lub wykonana została określona uprzednio liczba iteracji, algorytm kończy działanie, jako wynik podając najlepsze dostępne rozwiązanie. W przeciwnym wypadku dokonywana jest replikacja najlepszych osobników, oraz poddanie ich operacjom genetycznym, mającym na celu wprowadzić większą różnorodność genetyczną. Te chromosomy stanowią kolejną populację, a algorytm wraca do punktu ekspresji genów. Złożoność obliczeniowa jest więc szacowana przez   [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img006.svm}
 (g – liczba generacji w jednym przebiegu, f – liczba danych uczących). Szczegóły poszczególnych etapów przedstawione są poniżej.

\subsection[Otwarta ramka odczytu a gen]{\selectlanguage{polish} Otwarta ramka odczytu a gen}
Jak zostało wspomniane, w genetyce funkcjonuje pojęcie Open Reading Frame, oznaczające fragment genu rozpoczynający się kodonem startu, a kończący kodonem stopu. Pomiędzy nimi znajdują się informacje. To właśnie szukając ORFów odnajduje się pojedyncze geny. 

GEP odbiega odrobinę od takiego schematu. Podobnie, oprócz ORF w chromosomie mogą istnieć fragmenty niekodujące, jednak nie mamy do czynienia z kodonami początku i końca sekwencji. ORF zawsze zaczyna się bowiem na pierwszej pozycji, kończy zaś gdy drzewo wyrażenia jest kompletne. 

Niech za przykład posłuży następujący ciąg znaków:


\bigskip

\ \ 012345678

\ \ +++aba*ab


\bigskip

Traktując ten ciąg jako quasi-prefiksowy zapis wyrażenia algebraicznego, otrzymujemy drzewo:

\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img007.png}

\end{figure}
czyli wyrażenie (a+b)+(a+(a*b))


\bigskip

Rozumując w drugą stronę: każde wyrażenie (czy to algebraiczne, czy logiczne) da się przedstawić w postaci drzewa. Zczytując symbole od góry do dołu oraz od lewej do prawej, otrzymujemy ORF kodujący dane wyrażenie.

\ \ Rzeczą, która wyróżnia GEP na tle klasycznych algorytmów ewolucyjnych, jest struktura genów. Każdy gen składa się z tzw głowy oraz ogona. W części pierwszej znajdować się mogą zarówno symbole funkcyjne (należące do zbioru F), oraz symbole terminalne (należące do zbioru T), w ogonie zaś jedynie terminale. Długość głowy h ustalana jest odgórnie, w zależności od problemu, długość ogona t natomiast jest funkcją od h i wyraża się równaniem:


\bigskip

\ \ t = h(n-1)+1 


\bigskip

gdzie n \ jest maksymalną arnością spośród operatorów funkcyjnych. Dla przykładu, niech F=\{+,-,*,/\}, T=\{a,b\}, h=4. Wszystkie operatory arytmetyczne są dwuargumentowe, wobec tego n=2. Długość ogona wynosi więc t=4(1)+1=5. 

Podejście takie pozwala zapobiec powstawaniu drzew, dla których „nie starcza” terminali. Niezależnie bowiem od kierunku, w jaki pójdzie mutacja (bądź losowa inicjacja pierwszej populacji), ORF może stanowić zarówno cały gen (w przypadku, kiedy cała głowa składa się z symboli funkcyjnych), bądź też być jednoelementowa (druga skrajność: pierwszy element głowy jest symbolem terminalnym).


\bigskip

\subsection[Chromosomy wielogenowe]{\selectlanguage{polish} Chromosomy wielogenowe}
\ \ Jakkolwiek poprawnym jest używanie w algorytmie osobników będącym pojedynczym genem, lepsze wyniki można najczęściej osiągnąć stosując chromosomy wielogenowe. Pozwala to lepiej wykorzystać zalety wynikające z manipulacji na ciągu znaków przed sparsowaniem go na program. Liczba genów na chromosom, podobnie jak długość głowy, obierane są z góry dla danego problemu, bądź przebiegu algorytmu. Jako że każdy z genów traktowany jest jako poddrzewo całego drzewa powstałego z chromosomu, konieczne jest również wybranie funkcji spajającej poddrzewa w całość. Dla przykładu, niech chromosom składa się z dwóch poddrzew, h=4, t=5, F=\{+,-,*,/\}, T=\{a\}, funkcją spajającą niech będzie operacja dodawania. Tu, jak i w dalszej części, korzeń drzewa odpowiadający za funkcję łączącą oznaczony jest czerwoną obwódką. (Pionową kreską rozdzielone graficznie zostały poszczególne geny, jednak jedynie w celach poglądowych, w części operacji genetycznych chromosom jest bowiem traktowany jako jeden spójny ciąg znaków.)


\bigskip

\ \ 012345678{\textbar}012345678

\ \ ++a/aaaaa{\textbar}-a-*aaaaa


\bigskip


\bigskip



\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img008.png}

\end{figure}

\bigskip

W tym miejscu warto porównać GEP do bardziej tradycyjnych metod GP. W tych drugich operacje genetyczne wykonywane są na strukturze grafowej, tu – na ciągu znaków. Sprawia to, że z pozoru niewielka zmiana (np. mutacja jednego elementu) może spowodować znaczące zmiany w strukturze drzewa wynikowego.


\bigskip

\subsection[Selekcja i replikacja]{\selectlanguage{polish} Selekcja i replikacja}
\ \ Jedną z najważniejszych kwestii przy projektowaniu algorytmu ewolucyjnego jest wybór metody selekcji osobników do replikacji i utworzenia kolejnej generacji. W ogólności proces ten polega na wyborze osobników, które w danym momencie dają najlepsze wyniki, bądź są najlepiej rokujące, oraz ich skopiowaniu do następnej populacji, by następnie poddać je operacjom genetycznym.

\ Do oceny „jakości” osobnika służy funkcja przystosowania (ang. fitness function). Jej ustalenie jest zależne od specyfiki problemu. Zazwyczaj jej wartość przyrównywana jest do maksymalnej (bądź minimalnej) wartości idealnej. Kolejne iteracje algorytmu mają w efekcie prowadzić do podnoszenia (bądź obniżania) wartości fitness, tak by zbliżyć ją najbardziej jak to możliwe do wartości idealnej. Aby tego dokonać, rozpatrywany fenotyp przeciwstawiany jest szeregowi danych uczących (również danych treningowych bądź z ang. fitness cases), czyli danym mającym zweryfikować jego skuteczność. 

Istnieje co najmniej parę metod selekcji osobników, m. in. deterministyczna metoda rankingowa, czy metoda turniejowa, losująca pewną liczbę osobników podzielonych na grupy, następnie zostawiająca te względnie najlepsze spośród wybranych. Autorka systemu wybrała selekcję proporcjonalną zwaną metodą koła ruletki (ang. roulettewheel). Polega ona na przypisaniu fenotypów do pól wyimaginowanego koła ruletki. Wielkość pola jest wprost propocjonalna do wartości dostosowania osobnika. Następnie zachodzi losowanie (analogia do zakręcenia kołem ruletki), przy czym im większa wartość funkcji przystosowania, tym większe prawdopodobieństwo wyboru osobnika. Pseudokod algorytmu losowania przedstawiony jest poniżej

\ \ begin

\ \ \ \ r := random;

\ \ \ \ s := 0.0;

\ \ \ \ i := 0;

\ \ \ \ repeat

\ \ \ \ \ \ i := i+1;

\ \ \ \ \ \ s := s + ps[i]

\ \ \ \ until s {\textgreater}= r;

\ \ \ \ return(i);

\ \ end


\bigskip

Na początku losowana jest liczba z zakresu 0-100. Następnie dodawane są procentowe wartości dostosowania kolejnych osobników, dopóki suma nie przekroczy wylosowanej liczby. Jak widać, im większa liczba, tym większe prawdopodobieństwo zwrócenia osobnika o wysokiej wartości przystosowania. 


\bigskip

W porównaniu z innymi metodami selekcji, selekcja ruletkowa może dawać gorsze rezultaty (patrząc pod kontem faktycznej selekcji najlepszych osobników, przy jednoczesnym zachowaniu różnorodności genetycznej poprzez pozwolenie na replikację osobników słabszych), jednak przy wprowadzeniu „prostego elityzmu” (ang. simple elitism), polegającego na zachowaniu i replikacji bezwzględnie najlepszego osobnika, większość powszechnie stosowanych metod selekcji wykazuje podobne rezultaty, ze wskazaniem na koło ruletki przy bardziej skomplikowanych problemach ([3]).


\bigskip


\bigskip

\subsection[Modyfikacja]{\selectlanguage{polish} Modyfikacja}
\ \ Istotą algorytmów ewolucyjnych są wprowadzające element losowy modyfikacje populacji. W założeniach GEP, z wyjątkiem mutacji, żaden operator nie może modyfikować chromosomu więcej niż raz. Z drugiej strony, jeden chromosom może być modyfikowany przez więcej niż jeden operator, bądź też nie być zmieniany ani razu. Wszystkie procesy przebiegają losowo: zarówno w kwestii wyboru chromosomu, jak i sposobu przebiegu operacji. 

Wszystkie modyfikacje podlegają pewnym parametrom, dla przykładu, dla wskaźnika transpozycji (ang. transposition rate) równemu 0.7, siedem na dziesięć osobników zostanie wybranych do transpozycji.


\bigskip

\subsubsection[Mutacja]{\selectlanguage{polish} Mutacja}
Jest to najbardziej podstawowa forma modyfikacji. Polega na zamienieniu elementu na inny. Najpierw losowo wybierany jest chromosom, następnie, również losowo, element do mutacji, oraz element finalny. Jest to jedyny moment, w którym zagwarantować należy spójność danych, bo, chociaż mutacja może zajść w każdym miejscu, nie możliwe jest zmutowanie terminala z ogona w operator funkcyjny (w drugą stronę taka zamiana nie stanowi problemu). Zazwyczaj stosuje się dwie mutacje na jeden gen (mutowanie jednego jedynie symbolu w chromosomie mogłoby skutkować niewystarczającą zmianą różnorodności genetycznej).

Przykładowo nieh h=4, wybrane do mutacji symbole na pozycjach 0 i 11 mutują odpowiednio na a i Q (oznaczający pierwiastek kwadratowy)


\bigskip

\ \ 012345678{\textbar}012345678 \ \ \ \ \ 012345678{\textbar}012345678

\ \ +{}-*aaabaa{\textbar}**/+bbaab \ {}-{\textgreater} \ a{}-*aaabba{\textbar}*Q/+bbaab


\bigskip


\bigskip

[Warning: Draw object ignored]

\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img009.png}

\end{figure}
\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img010.png}

\end{figure}

\bigskip


\bigskip

Jak widać, mimo że zmiany nastąpiły tylko w dwóch miejscach, skutki są znaczące, gdyż zamiast wyrażenia 


\bigskip

\ \   [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img011.svm}
 


\bigskip

otrzymujemy


\bigskip

\ \   [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img012.svm}
 


\bigskip

Zaznaczyć tu należy, że autorka algorytmu w implementacji stosuje mutację dwupunktową, to znaczy w przy każdorazowej realizacji tego modyfikatora mutowane są dwie pozycje w genie. W aplikacji użytej jako narzędzie na potrzeby niniejszej pracy użyłem mutacji jednopunktowej m. in celem sprawdzenia różnic w otrzymanych wynikach. Brak ten jest niejako „nadrabiany” zwiększeniem częstotliwości występowania tej operacji.

\subsubsection[Transpozycja]{\selectlanguage{polish} Transpozycja}
Transpozonem nazywamy fragment genomu, który ulega transportowi, a dokładniej skopiowaniu i przesunięciu w obrębie chromosomu. W technice tej rozróżniane są trzy typy transpozycji:

\begin{itemize}
\item \begin{itemize}
\item transpozycja fragmentu zawierającego funkcje i terminale w dowolne miejsce w głowie, nie uwzględniając jednak korzenia poddrzewa, \ ang. insertion sequence elements (w odniesieniu do transpozonu – dalej jako IS, lub w odniesieniu do transpozycji – IST),
\item transpozycja takiegoż fragmentu, jednak miejscem docelowym staje się korzeń genu, ang. root insertion sequence elements (jak wyżej, odpowiednio RIS i RIST)
\item transpozycja całego genu na początek chromosomu.(dalej GT, ang. gene transposition)
\end{itemize}
\end{itemize}
Rozróżnienie między IS i RIS, wg Autorki, jest pozostałością z okresu rozwoju metody, kiedy to rozpatrywane były jedynie chromosomy jednogenowe. Mimo to zostały pozostawione w wersji ostatecznej, gdyż w sposób obrazowy potrafią przedstawić mechanizmy ewolucyjne. Z drugiej zaś strony, po sparametryzowaniu przebiegu algorytmu, rozróżnienie takie pozwala na lepszą jego kontrolę i „dostrojenie”. 

Podobnie jak w przypadku mutacji, tutaj również występują pewne różnice w wykorzystaniu modyfikacji między moją aplikacją a propozycją Ferreiry. Mianowicie Autorka stosuje trójstopniową transpozycję \ IS i RIS, stosując kolejno transpozon jedno-, dwu- i trójelementowy przy każdorazowym wywołaniu operacji. W swojej implementacji zastosowałem transpozycję pojedynczą z zastosowaniem tranzpozonu o długości równej 3, zakładając, tak jak przy mutacji, że odpowiedni dobór parametrów zniweluje tą różnicę.


\bigskip

\paragraph[Transpozycja IS]{\selectlanguage{polish} Transpozycja IS}
Transpozon przy IST może być każdy fragment. Jego początek losowany jest spośród wszystkich pozycji w obrębie chromosomu. Podobnie losowo wybierana jest jego długość. Destynacja nie może być już w takim samym stopniu dowolna, więc losowanie ogranicza się do pozycji w głowach genów, z wyjątkiem ich korzeni. Zazwyczaj do IST stosuje się trzy sekwencje IS różnej długości

Po dokonaniu losowań, transpozon jest kopiowany i przenoszony w odpowiednie miejsce. Fragment głowy znajdujący się za pozycją docelową zostają przesunięte do tyłu, tak daleko, jak pozwala na to długość głowy. Dla przykładu, rozpatrzmy chromosom dwugenowy, niech h=8, do transpozycji wybrany został element b+b na pozycji 7 w genie drugim, zaś docelowym miejscem została pozycja 4 w genie pierwszym. Otrzymujemy:


\bigskip

\ \ 01234567890123456{\textbar}01234567890123456

\ \ {}-+a-/*+Qabbabbaaa{\textbar}*-Qb+*b+babbaaaab

[Warning: Draw object ignored]


\bigskip


\bigskip

\ \ 01234567890123456{\textbar}01234567890123456

\ \ {}-+a-b+b/*bbabbaaa{\textbar}*-Qb+*b+babbaaaab


\bigskip

[Warning: Draw object ignored]\ \ \ \ \ \ \ \ 

\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img013.png}

\end{figure}
\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img014.svm}

\end{figure}

\bigskip



\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img015.png}

\end{figure}
\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img016.svm}

\end{figure}

\bigskip


\bigskip


\bigskip


\bigskip

Jak widać, transpozycja w sposób znaczący wpłynęła na strukturę pierwszego genu, jednocześnie będącego w dalszym ciągu poprawną syntaktycznie i logicznie konstrukcją. Wynika to z tego, że – by zachować rzeczoną spójność i nie dopuścić do rozszerzenia się głowy – usunięty został fragment +Qa. Część przed punktem transpozycja, jak i ogon pozostały bez zmian.


\bigskip

\paragraph[Transpozycja z korzeniem.]{\selectlanguage{polish} Transpozycja z korzeniem.}
RIST różni się od poprzedniej operacji tym, że jej celem są zmiany w dolnych częściach drzewa, od korzenia poczynając. Z racji więc na tą specyfikę, początkiem transposonu musi być operator funkcyjny\footnote{Jak zostało wspomniane, rozdzielenie IST i RIST jest reliktem wczesnych wersji algorytmu i miało charakter raczej praktyczny, niż wynikający z konieczności zachowania prawidłowego jego działania. Teoretycznie więc niezapewnienie genowi korzenia funkcyjnego nie wpłynęłoby na poprawność genu. }. Przebieg algorytmu podobny jest do transpozycji IS, z dwiema różnicami. Zamiast losowania destynacji spośród całego chromosomu, wybiera się jedynie gen, na którego początku podstawiony zostanie transpozon. Po drugie, przy losowaniu początku transpozonu, o ile symbol na wylosowanej pozycji nie jest operatorem funkcyjnym, wskaźnik przesuwany jest o jedną pozycję w stronę ogona, tak długo, aż na taki operator trafi. Jeśli to nie nastąpi, transpozycja nie następuje. 

Przykładowo, niech wybrany skopiowania będzie fragment +bQ wylosowanym genem zaś gen drugi, z którego transpozon pochodzi:


\bigskip

\ \ 01234567890123456{\textbar}01234567890123456

\ \ {}-+-a/++/abaaabaaa{\textbar}*a++bQ{}-/babbababb

[Warning: Draw object ignored]


\bigskip

\ \ 01234567890123456{\textbar}01234567890123456

\ \ {}-+-a/++/abaaabaaa{\textbar}+bQ*a++bbabbababb

[Warning: Draw object ignored]

\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img017.png}

\end{figure}

\bigskip



\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img018.png}

\end{figure}
Jak widać, zamiana taka drastycznie wpływa na fenotyp. Zachowanie „tylnej” części głowy pozostaje takie samo, jak w przypadku IST. Warto też zauważyć, że w usuwanej część głowy znalazł się też oryginał transpozonu. 


\bigskip

\paragraph[Transpozycja genu]{\selectlanguage{polish} Transpozycja genu}
W tym przypadku, transpozonem jest cały gen. Zostaje on niejako przesunięty na początek chromosomu, ponieważ, w przeciwieństwie do poprzednich przypadków, tu oryginał jest usuwany. Jest to dosyć oczywiste rozwiązanie, biorąc pod uwagę przesunięcie genu uprzednio pierwszego.

Na przykład w wariancie trzygenowym:


\bigskip

\ \ 01234567890123456{\textbar}01234567890123456{\textbar}01234567890123456

\ \ *+a/+/+Qaabbababb{\textbar}/+b/+Q*/abbabbaab{\textbar}{}-Q—-Q-Qaaabbababb


\bigskip

\ \ 01234567890123456{\textbar}01234567890123456{\textbar}01234567890123456

\ \ {}-Q—-Q-Qaaabbababb{\textbar}*+a/+/+Qaabbababb{\textbar}/+b/+Q*/abbabbaab


\bigskip


\bigskip

W przypadku problemów arytmetycznych, gdzie funkcją spajającą jest operator dodawania bądź mnożenia taka transpozycja może nie dawać wielkich efektów, jednak przy zagadnieniach logicznych, bądź operatory logiczne wykorzystujące, skutki zamiany mogą być co najmniej znaczące. Niech posłuży nam przykład: niech F=\{I,N,A,O\}, oznaczające odpowiednio IF („jeśli”, trójargumentowa I(X,Y,Z) := jeśli X to Y, w przeciwnym razie Z), NOT (logiczne zaprzeczenie), AND (koniunkcja), O (alternatywa). Niech też operatorem łączącym będzie IF. W takim przypadku, transpozycja genu trzeciego, skutkująca postawienia go w roli logicznego poprzednika implikacji, zaś z uprzedniego genu w pozycji następnika implikacji, kompletnie zmienia efekty działania programu wynikowego.


\bigskip

\subsubsection[Krzyżowanie]{\selectlanguage{polish} Krzyżowanie}
W naturze krzyżowanie, czyli rozmnażanie płciowe, w największym stopniu odpowiada za zwiększanie różnorodności genetycznej. Stąd też, będący niejako jego odpowiednikiem, modyfikator krzyżowania (rekombinacji), posiada często wysoki parametr odpowiadający za prawdopodobieństwo jego wystąpienia. Rekombinacja operuje na dwóch chromosomach. \ Jak wyżej, wyróżnia się trzy typy krzyżowania:

\begin{itemize}
\item \begin{itemize}
\item rekombinacja jednopunktowa (ang. one-point recombination, dalej 1PR)
\item \ // dwupunktowa (ang. two-points recombination, dalej 2PR)
\item \ // genu (ang. gene recombination, dalej GR)
\end{itemize}
\end{itemize}
Jak we wszystkich modyfikacjach, wszelkie wybory, zarówno chromosomów-rodziców, jak i pozostałych parametrów, dokonywane są losowo.


\bigskip

\paragraph[Krzyżowanie jednopunktowe]{\selectlanguage{polish} Krzyżowanie jednopunktowe}
Operacja ta polega na zmianie skrzyżowaniu ze sobą dwóch chromosomów. Jest to modyfikacja o tyle ciekawa, że nie ma tu znaczenia podział chromosomów na geny\footnote{Co prawda, w implementacji ten podział jest uwzględniony, jednak wynika to przyjętej przez mnie metody reprezentacji danych i jest kwestią wtórną.}. Przebieg jest następujący: losowany jest punkt, w którym oba chromosomy zostają „przecięte”, następnie elementy znajdujące się za punktem przecięcia „zamieniają się miejscami”. Najlepiej zaprezentuje to przykład: niech punktem wylosowanym będzie pozycja 2 w genie drugim (podział między genami zaznaczają jedynie numery pozycji, separatorów nie użyłem, by nie zaciemniać obrazu):


\bigskip

\ \ 012345678012345678012345678

\ \ QQa-aababQ+-aaababaab-bbaaa

\ \ Q-a/baaaaQa-+aaaab/aa-baaaa


\bigskip


\bigskip

\ \ 012345678012345678012345678

\ \ QQa-aababQ+{}-+aaaab/aa-baaaa

\ \ Q-a/baaaaQa{}-aaababaab-bbaaa


\bigskip


\bigskip

\paragraph[Krzyżowanie dwupunktowe]{\selectlanguage{polish} Krzyżowanie dwupunktowe}
Ten rodzaj modyfikacji, różni się od poprzedniego faktem, że podział chromosomów macierzystych następuje w dwóch miejscach, dzieląc je na trzy części. Fragment środkowy służy tu za materiał genetyczny, który jest wymieniany\footnote{Faktycznie nie ma znaczenia, czy wymieniany jest fragment środkowy, czy skrajne, wszak kolejność chromosomów w populacji jest dowolna.}. Ponownie, posłużę się przykładem (niech wybranymi punktami rekombinacji będą pozycje 3. w genie 1. i 5. w genie 3.):


\bigskip


\bigskip

\ \ 012345678012345678012345678

\ \ {}-a-*abbbbaa-abbaaa*/a*bbbba

\ \ Q*/aabaaaaQ/Qaabbbbbb-abaab


\bigskip


\bigskip

\ \ 012345678012345678012345678

\ \ {}-a-*abaaaaQ/Qaabbbbbb-abbba

\ \ Q*/aabbbbaa-abbaaa*/a*bbaab


\bigskip


\bigskip

Krzyżowanie dwupunktowe daje o wiele większe możliwości uzyskiwania nowych, różnych osobników, niż wariant jednopunktowy. Co należy zauważyć, w przypadku gdy podział następuje w częściach ogonowych, ingerencja w strukturę poddrzew jest niewielka, i podobna jest do niżej opisanej wymiany genów, z dodatkową (potencjalną) zmianą układu terminali na liściach poddrzew.


\bigskip

\paragraph[Krzyżowanie genów]{\selectlanguage{polish} Krzyżowanie genów}
Ostatnim wariantem modyfikatora jest rekombinacja genów. Losowo wybrany gen \ zamieniany jest ze swoim odpowiednikiem w drugim rodzicu. Przykład (niech genem wylosowanym do krzyżowania będzie gen pierwszy):


\bigskip

\ \ 012345678{\textbar}012345678{\textbar}012345678

\ \ +Q/Qabbbb{\textbar}QQb*ababa{\textbar}*a**bbaaa

\ \ {}-*Qaaaabb{\textbar}+b/*ababa{\textbar}-ab/babba


\bigskip


\bigskip

\ \ 012345678{\textbar}012345678{\textbar}012345678

\ \ {}-*Qaaaabb{\textbar}QQb*ababa{\textbar}*a**bbaaa

\ \ +Q/Qabbbb{\textbar}+b/*ababa{\textbar}-ab/babba


\bigskip

GR, choć nie tworzy on nowego materiału genetycznego (żadna ORF nie jest naruszana), jest to istotny modyfikator. Podobnie jak GT, najciekawsze wyniki wykazuje przy użyciu operatorów logicznych. Mimo to, używanie go jako jedynego (a w każdym razie wiodącego) modyfikatora wymaga znacznej wielkości populacji początkowej, gdyż w przeciwnym razie ciężko byłoby zagwarantować wystarczającą różnorodności genetyczną.


\bigskip

\section[Rozpatrywane problemy]{\selectlanguage{polish} Rozpatrywane problemy}

\bigskip

W poniższym rozdziale zaprezentowane zostaną przykłady zastosowań mechaniki GEP. W żadnej mierze nie wyczerpują one możliwości tej techniki, pokazują jednak jak sprawdza się ona w praktyce. Dokładniejsza analiza wyników uzyskiwanych w zależności od parametryzacji znajduje się w rozdziale 4.


\bigskip

\subsection[Odnajdywanie funkcji ]{\selectlanguage{polish} Odnajdywanie funkcji }
Problem znajdowania funkcji na podstawie podanych jej wartości dla konkretnych argumentów (również z ang. „symbolic regression”) jest jednym z podstawowych i najprostszych przykładów użycia algorytmu GEP. W przypadku tym za dane treningowe posłużą pary a,f(a), gdzie a jest losową liczbą rzeczywistą (bądź zespoloną, lecz to implikuje konieczne modyfikacje struktury chromosomu), f(a) zaś wartością szukanej funkcji dla a. Aby zapewnić prawidłowe działanie, używa się także pewnej niewielkiej tolerancji na błąd. \ Funkcja przystosowania przyjęta przez Ferreirę wyraża się wzorem:

  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img019.svm}
 \ \ (1)

bądź 

  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img020.svm}
 \ \ (2)

dla

  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img021.svm}
 {}- wartość funkcji fitness dla i{}-tego chromosomu, 

  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img022.svm}
 {}- liczba danych treningowych,

  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img023.svm}
 {}- wartość wyliczona przez i{}-ty chromosom dla j{}-tego fitness case,

  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img024.svm}
 {}- faktyczna wartość funkcji szukanej dla j{}-tego fitness case,

  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img025.svm}
 {}- zakres selekcji.

Wzór zależny jest od tego, czy błąd rozpatrujemy bezwzględnie (1), czy względnie (2). Funkcja taka prezentuje rozbieżność między wynikiem otrzymanym przez chromosom, a faktycznym wynikom bezwzględnie, bądź procentowo. 


\bigskip

Niech za przykład posłuży tu prosta funkcja wielomianowa   [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img026.svm}
 , zaś za dane treningowe posłużyły pary przedstawione w tabeli 1.

Tabela 1

\begin{center}
\tablefirsthead{}
\tablehead{}
\tabletail{}
\tablelasttail{}
\begin{supertabular}{|m{4.6150002cm}|m{4.695cm}|}
\hline
\centering{\selectlanguage{polish} a} &
\centering\arraybslash{\selectlanguage{polish} f(a)}\\\hline
\centering{\selectlanguage{polish} {}-4.2605} &
\centering\arraybslash{\selectlanguage{polish} 46.9346 }\\\hline
\centering{\selectlanguage{polish} {}-2.0437} &
\centering\arraybslash{\selectlanguage{polish} 9.44273 }\\\hline
\centering{\selectlanguage{polish} {}-9.8317} &
\centering\arraybslash{\selectlanguage{polish} 271.324 }\\\hline
\centering{\selectlanguage{polish} 1.02.7429} &
\centering\arraybslash{\selectlanguage{polish} 29.0563 }\\\hline
\centering{\selectlanguage{polish} 0.7328} &
\centering\arraybslash{\selectlanguage{polish} 4.07659 }\\\hline
\centering{\selectlanguage{polish} {}-8.6491} &
\centering\arraybslash{\selectlanguage{polish} 208.123 }\\\hline
\centering{\selectlanguage{polish} {}-3.6101} &
\centering\arraybslash{\selectlanguage{polish} 32.8783 }\\\hline
\centering{\selectlanguage{polish} {}-1.8999} &
\centering\arraybslash{\selectlanguage{polish} 8.02906 }\\\hline
\centering{\selectlanguage{polish} {}-4.8852} &
\centering\arraybslash{\selectlanguage{polish} 62.8251 }\\\hline
\centering{\selectlanguage{polish} 1.07.3998} &
\centering\arraybslash{\selectlanguage{polish} 180.071}\\\hline
\end{supertabular}
\end{center}

\bigskip


\bigskip


\bigskip

  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img027.svm}
 F=\{-,+,*,/,Q\}, T=\{a\}

W tym miejscu należy zaznaczyć, że funkcja pierwiastka kwadratowego stosowana jest z pewnym zabezpieczeniem przed błędem dziedziny, mianowicie jeśli argument jest mniejszy od zera, funkcja zwraca zero.

Użyte parametry (modification rates):

Tabela 2.

\begin{center}
\tablefirsthead{}
\tablehead{}
\tabletail{}
\tablelasttail{}
\begin{supertabular}{|m{4.589cm}|m{4.695cm}|}
\hline
{\selectlanguage{polish} mutacja:} &
{\selectlanguage{polish} 0.5}\\\hline
{\selectlanguage{polish} IST:} &
{\selectlanguage{polish} 0.2}\\\hline
{\selectlanguage{polish} RIST:} &
{\selectlanguage{polish} 0.3}\\\hline
{\selectlanguage{polish} GT:} &
{\selectlanguage{polish} 0.2}\\\hline
{\selectlanguage{polish} 1PR:} &
{\selectlanguage{polish} 0.2}\\\hline
{\selectlanguage{polish} 2PR:} &
{\selectlanguage{polish} 0.2}\\\hline
{\selectlanguage{polish} GR:} &
{\selectlanguage{polish} 0.1}\\\hline
{\selectlanguage{polish} wielkość populacji:} &
{\selectlanguage{polish} 10os.}\\\hline
{\selectlanguage{polish} liczba genów w chromosomie:} &
{\selectlanguage{polish} 3;}\\\hline
{\selectlanguage{polish} h} &
{\selectlanguage{polish} 4}\\\hline
{\selectlanguage{polish} liczba generacji:} &
{\selectlanguage{polish} 50\footnotemark{}}\\\hline
\end{supertabular}
\end{center}
\footnotetext{Faktycznie liczba populacji wynosiła 51, gdyż początkowa generacja została liczona jako zerowa.}

\bigskip

Do wyliczenia fitness użyty został wzór (.1), zaś margines błędu ustalony został na 0.01 w skali chromosomu dla każdego fitness case. W jednym z udanych\footnote{Za udany uznaję tu przebieg, w którym odnaleziona została prawidłowa funkcja, tzn chromosom z fitness = 1000} przebiegów algorytmu, rozwiązanie zostało odnalezione w generacji dziesiątej. 


\bigskip

Początkowa losowa populacja:


\bigskip

gen 1. \ \ {\textbar} gen 2. \ {\textbar} gen 3. \ {\textbar} \ \ fitness\ \ 

aaaaaaaaa{\textbar}/a+/aaaaa{\textbar}QQa/aaaaa{\textbar} : 139.093

/aa+aaaaa{\textbar}+a**aaaaa{\textbar}*/a*aaaaa{\textbar} : -1579.7

aa+aaaaaa{\textbar}aaQaaaaaa{\textbar}*aaaaaaaa{\textbar} : 395.753

aa/*aaaaa{\textbar}+aa*aaaaa{\textbar}a+a/aaaaa{\textbar} : 50.0205

{}-aQaaaaaa{\textbar}*/*+aaaaa{\textbar}/a/+aaaaa{\textbar} : 699.796

a+aaaaaaa{\textbar}aaaQaaaaa{\textbar}+Q*+aaaaa{\textbar} : 403.153

a-Qaaaaaa{\textbar}QQaaaaaaa{\textbar}Q-aaaaaaa{\textbar} : 126.796

Qaa*aaaaa{\textbar}aaa/aaaaa{\textbar}a*aaaaaaa{\textbar} : 103.862

aaa-aaaaa{\textbar}Qaaaaaaaa{\textbar}Qa+*aaaaa{\textbar} : 133.4

a/aaaaaaa{\textbar}//+aaaaaa{\textbar}++**aaaaa{\textbar} : 692.833


\bigskip

Jak widać, początkowe wartości dalekie są od zadowalających. Jednak, jak widać na wykresie\footnote{Dane do wykresu oraz szczegółowy zapis przebiegu algorytmu w załączniku nr}, już w drugiej generacji znaleziony został fenotyp bliski ideałowi (fitness \ = 955,945), przy czym średnia wartość przez cały czas nie odbiega znacząco od średniej początkowej.



\begin{figure}
\centering
\begin{minipage}{15.423cm}

\bigskip

Wykres \stepcounter{Wykres}{\theWykres}: Zachowanie funkcji fitness dla problemu szukania funkcji
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img028.svm}
\end{minipage}
\end{figure}

\bigskip

Generacja finalna, zawierająca poprawne rozwiązanie:


\bigskip

\ \ gen 1.\ \ {\textbar}\ \ gen 2.\ \ {\textbar}\ \ gen3.\ \ {\textbar}\ \ fitness

*/a*aaaaa{\textbar}/a+aaaaaa{\textbar}++**aaaaa{\textbar} : 955.945

/aaaaaaaa{\textbar}Qaaaaaaaa{\textbar}/aaQaaaaa{\textbar} : 172.472

//+*aaaaa{\textbar}+aaaaaaaa{\textbar}a*+aaaaaa{\textbar} : 79.3252

//+*aaaaa{\textbar}+aaaaaaaa{\textbar}a*+aaaaaa{\textbar} : 79.3252

//+*aaaaa{\textbar}+aaaaaaaa{\textbar}a*+aaaaaa{\textbar} : 79.3252

+aaaaaaaa{\textbar}+aaaaaaaa{\textbar}+aaaaaaaa{\textbar} : 0.7707

//+*aaaaa{\textbar}+aaaaaaaa{\textbar}a//+aaaaa{\textbar} : 79.3252

//+*aaaaa{\textbar}+aaaaaaaa{\textbar}a-+aaaaaa{\textbar} : 79.3252

//+*aaaaa{\textbar}//aaaaaaa{\textbar}*+aaaaaaa{\textbar} : 746.4

//a*aaaaa{\textbar}*+a+aaaaa{\textbar}+aaaaaaaa{\textbar} : 1000


\bigskip

Mimo iż przedstawiony problem nie był skomplikowany, nie w każdym z eksperymentów (przy podanych parametrach) rozwiązanie jest odnajdywanie, choć w większości przypadków wyniki bardzo bliskie są szukanej funkcji. Niech za przykład posłuży przebiega algorytmu, w którym sukces nie został osiągnięty. Przy identycznych parametrach, w już w drugiej populacji wyewoluował osobnik o dostosowaniu niezmiernie zbliżonym do maksimum. Po kolejnych \ dziewięciu iteracjach powstał chromosom, który pierwszeństwo zachował do końca działania algorytmu. Rzeczony chromosom oraz jego fenotyp:


\bigskip

\ \ \ \ +**+aaaaa\ \ {\textbar}\ \ aaa*aaaaa\ \ {\textbar}\ \ \ \ aaaaaaaaa


\bigskip



\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img029.png}

\end{figure}
\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img030.svm}

\end{figure}
Wykres 2. przedstawia przebieg funkcji dostosowania w przebiegu, w którym rozwiązanie takie zostało odnalezione, wykres obu funkcji (odnalezionej, oznaczonej kolorem czerwonym, oraz docelowej, oznaczonej kolorem niebieskim) przedstawiony jest na wykresie 3.


\bigskip



\begin{figure}
\centering
\begin{minipage}{16cm}
Wykres \stepcounter{Wykres}{\theWykres}: Przebieg funkcji dostosowania
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img031.svm}
\end{minipage}
\end{figure}


\begin{figure}
\centering
\begin{minipage}{13.229cm}
Wykres \stepcounter{Wykres}{\theWykres}: Kolorem niebiskim oznaczona została funkcjia szukana, czerwonym zaś funkcja odnaleziona
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img032.png}
\end{minipage}
\end{figure}

\bigskip


\bigskip


\bigskip

Dokładniejsza analiza wyników uzyskiwanych przez GEP dla problemu znajdowania funkcji znajduje się w poniżej.


\bigskip

\subsection[Problemy klasyfikacyjne]{\selectlanguage{polish} Problemy klasyfikacyjne}
Mechanizm GEP można także z powodzeniem wykorzystywać w problemach związanych ze zgłębianiem danych, w szczególności w zagadnieniach klasyfikacyjnych. Klasyfikacja polega (w pewnym uproszczeniu) na odgadnięciu parametru docelowego na podstawie parametrów znanych (przesłanek). Zazwyczaj stosuje się implikację JEŚLI {\textless}przesłanki{\textgreater} TO {\textless}wniosek{\textgreater}, gdzie wniosek to klasa do jakiej zaliczamy rozpatrywaną jednostkę (entity). W tym przypadku również stosuje się tzw dane uczące. Jako funkcję przystosowania przyjmuje się zazwyczaj stosunek przypadków zaklasyfikowanych prawidłowo do przypadków zaklasyfikowanych błędnie. W implementacji użyłem metody zaproponowanej przez Lopesa ([6]). Funkcja jest iloczynem dwóch wartości: czułości (ang. Sensitivity) Se i swoistości (bądź specyficzność, ang. specificity) Sp określających skuteczność prawidłowego rozpoznania \ odpowiednio przypadków poprawnie uznanych jako należące do swojej klasy (true positive, „faktycznie dodatnich”) i poprawnie z odpowiedniej klasy wykluczonych (true negative, „faktycznie ujemnych”). Niech za ilustrację tych pojęć posłuży przykład diagnozy medyczne, gdzie przyjmujemy dwie klasy: wykrycie choroby (diagnoza pozytywna), bądź uznanie pacjenta za zdrowego (diagnoza negatywna). Za wynik faktycznie dodatni uznamy prawidłowe wykrycie o pacjenta choroby, zaś fałszywie dodatni – orzeczenie u zdrowego pacjenta choroby. Analogicznie, wynikiem prawdziwie ujemnym będzie uznanie zdrowym pacjenta zdrowego, z kolei fałszywie ujemnym – nie wykrycie choroby u pacjenta na nią cierpiącego. Parametry te określa się wzorami:

  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img033.svm}
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img034.svm}
 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)


\bigskip

gdzie tp oznacza liczbę przypadków faktycznie dodatnich, tn – faktycznie ujemnych, fp – błędnie dodatnich, fn – błędnie ujemnych. W analogi do szpitala, czułość równa 1 oznacza, że wszyscy pacjenci chorzy zostaną jako tacy oznaczeni, zaś specyficzność o tej wartości oznacza, że wszyscy zdrowi pacjenci zostaną „zwolnieni do domu”.


\bigskip

Ze względu na typ wartości parametrów, problemy klasyfikacyjne można podzielić na problemy z parametrami logicznymi i rzeczywistymi. Drugim rozróżnieniem może być liczba klas. 

Jeśli wartościami terminalnymi mogą zostać jedynie logiczne prawda i fałsz, problem zdaje się być trywialny, wystarczy wykorzystać operatory logiczne bezpośrednio na terminalach z tego zbioru . Inaczej wygląda to, jeśli algorytm działać ma na wartościach rzeczywistych. Ferreira w [1] proponuje niezmodyfikowaną wersję algorytmu. Za przykład podając test diagnostyczny na typ raka piersi (opisane szerzej w rozdziale 5.3), wykorzystuje zbiór operatorów funkcyjnych F=\{+, -, *, /, {\textless}, {\textgreater}, :, \$, =, !\} , gdzie ostatnie sześć symboli oznacza odpowiednio mniejszy od, większy od, mniejszy lub równy, większy lub równy, różny. Po wykonaniu porównania, jeśli wynikiem jest prawda, zwracana jest pierwsza wartość, jeśli fałsz – druga. Za funkcję przystosowania Autorka przyjęła implikację:

  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img035.svm}
 

W eksperymencie przez nią opisywanym wykorzystano zestaw 350-ciu danych treningowych, oraz 174 danych testowy. Wynikiem diagnostyki może być jedna z dwóch klas: B – nowotwór łagodny (ang. „benign tumer”) oraz M – nowotwór złośliwy (ang. „malignant”). Osobniki mają tu postać chromosomów trójgenowych, przy czym każdy z genów odpowiada za osobną regułę. 

Z racji tego, że liczba klas równa jest 2, interpretacja wyniku zwracanego przez regułę (będącego liczbą rzeczywistą) nie stanowi wielkiego problemu. Zastosowany został próg zaokrąglenia zero-jedynkowego (ang. 0/1 rounding threshold) Rt, powyżej którego za wynik przyjmuje się wartość 1, poniżej zaś – 0. W tym przypadku, Rt=0.

Algorytm został uruchomiony dla populacji składającej się z 50-ciu osobników o długości glowy h=8. Rozwiązanie oraz jego fenotyp przedstawione zostało na rysunku 4. 



\begin{figure}
\centering
\begin{minipage}{10.478cm}
Rysunek \stepcounter{Drawing}{\theDrawing}: a) chromosom będący wynikiem testu diagnostycznego, oraz b) jego fenotyp w formie drzew (źródło: [2]
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img036.gif}
\end{minipage}
\end{figure}
Rozwiązanie to spośród 350 danych treningowych poprawnie oznaczyło 340 z nich, zaś spośród 174 danych testowych osiągnęło 173 poprawnych wyników, co daje błąd klasyfikacyjny równy 0,575\%, skuteczność zaś równą 97,143\%. 


\bigskip

Innym z możliwych rozwiązań jest to zaproponowane przez autorów systemu GEPCLASS ([5]). W tym przypadku, podobnie jak w przytoczonym w rozdziale [] przykładzie, użyty został zbiór symboli funkcyjnych F=\{I,O,A,N\} oznaczających odpowiednio implikacji, alternatywie, koniunkcji i zaprzeczeniu. Ponadto, jak wyżej, znak „!” używany będzie jako relacja różności. 

Autorzy założyli, że liść stanowić będzie strukturę dwuelementową, złożoną z parametru, oraz numeru atrybutu. Takie podejście pociąga jednak za sobą daleko idące zmiany zarówno strukturze osobników i w mechanizmach modyfikacji, jak i w implementacji, wprowadza bowiem dodatkowy zbiór operatorów relacyjnych. Stanowią one niejako trzeci człon genu (po głowie i ogonie). 

Przykładowa ORF oraz drzewo parsowania prezentujące takie podejście przedstawione zostały na rysunku 5.


\bigskip

pozycja: \ \  \ 0 1 2 3 \ 4 \ \ 5

wartość:\ \  \ \  \ O N = {\textless} b{\textbar}2 a{\textbar}3

fenotyp:\ \ \ \  \ (\~{}b{\textless}2 OR a=3)



\begin{figure}
\centering
\begin{minipage}{11.511cm}
Rysunek \stepcounter{Drawing}{\theDrawing}: Otwarta ramka odczytu, fenotyp oraz jego reprezentacja na drzewie
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img037.png}
\end{minipage}
\end{figure}
Bazując na tej metodzie, użyłem podobnego rozwiązania. Z jednej strony, pokazuje ono elastyczność modelu GEP, z drugiej zaś może okazać się skuteczniejsze niż propozycja Ferreiry w przypadkach, o parametrach parami różnych o rzędy wielkości.

Nadal konieczne są tu modyfikacje działania, ale nie są tak daleko idące. Przede wszystkim zmieniona zostaje struktura genu, oraz jego translacji. Tutaj operatory relacyjne umieszczane są w terminalach, jednak nałożone zostają pewne restrykcje. Niech więc gen zapisany zostanie w postaci:


\bigskip

pozycja\ \ :\ \ 0 1 \ 2 \ \ 3 \ \ 4 \ \ 5 \ \ 6

wartość \ : \ \ I I a=1 b=2 c=3 d=3 e=4


\bigskip

Przy takim podejściu, liście stają trójką \{a,r,n\} gdzie a jest termem, r należy do zbioru operatorów relacyjnych, n zaś oznacza identyfikator z tablicy wartości danego parametru spośród wszystkich danych uczących. Oznacza to, że w implementacji konieczne jest uprzednie zczytanie przechowywanie owych wartości (przechowywane są jedynie wartości unikalne, tzn żadna wartość nie powtarza się w tablicy, dane nie są również poddane sortowaniu, które znacznie zwiększałoby złożoność obliczeniową algorytmu). 

Powyższy gen jest więc tłumaczony na poniższe drzewo:


\bigskip



\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img038.png}

\end{figure}
Zakładając taką strukturę genów, zmiany w operacjach modyfikacji mają charakter jedynie implementacyjny.


\bigskip

Sam fenotyp nie zawsze daje jednak odpowiedzi, do której klasy zaklasyfikować rozpatrywany. przypadek. W przypadku, gdy rezultatem może być jedynie wartość prawda bądź fałsz, problem nie zachodzi, ponieważ poddrzewa takież wartości zwracają (można by wręcz potraktować to jako szczególny przypadek szukania funkcji, przy czym parametry mają wartości zero-jedynkowe). Inaczej jest jednak gdy klas jest więcej, żadne poddrzewo nie może jednoznacznie wskazać numeru klasy. Jednym z możliwych rozwiązań jest założenie, że każdy gen w chromosomie odpowiada konkretnej klasie. Liczba genów jest więc równa liczbie klas. Przykładowo, niech dany będzie zbiór klas \{C1, C2, C3\} oraz chromosom:


\bigskip

gen\ \  \ Ia!8a{\textless}10a=5d{\textgreater}1d{\textless}4a{\textless}3{\textbar}OIc=3a=7c{\textless}2b{\textgreater}0b!3{\textbar}d!2Oa{\textgreater}1b{\textless}7c{\textgreater}2a!7c{\textgreater}3

wartość \ \  \ \ \ \ T\ \ \ \ \ \  \ \ \ \ T\ \ \ \ \ \  \ \ \ \ F


\bigskip

gdzie T oznacza logiczną prawdę, F zaś fałsz. Rozpatrywany przypadek z danych uczących należy do klasy C2, co zostało prawidłowo rozpoznane przez gen drugi (tp). Gen trzeci również dał prawidłową odpowiedź, zwracając wartość fałsz (tn), „pomylił” się jednak gen pierwszy, zwracając prawdę (fp) (mimo iż każdy fitness case jest liczony niejako trzy razy, proporcje Se i Sp pozostają bez zmian).


\bigskip

Przykładowy rezultat uzyskany dla problemu klasyfikacji odmiany irysów\footnote{Iris Plants Database, R.A. Fisher 1988, \ dane w załączniku [?]}. Jako danych treningowych użyto zestawu stu pięćdziesięciu przypadków składających się z czterech parametrów, oraz klasy. Parametry liczbowe opisują tu cechy kielicha kwiatu, odpowiednio długość (a) i szerokość (b) działki kielicha oraz długość (c) i szerokość (d) płatka, wyrażane w centymetrach. Wynikiem wnioskowania może być jedna z trzech klas: Iris setosa, Iris versicolor oraz Iris virginica. Na każdą odmianę przypadało 50 zestawów danych. Algorytm zostało uruchomiony z następującymi parametrami zawartymi w tabeli 3.

Tabela 3.

\begin{center}
\tablefirsthead{}
\tablehead{}
\tabletail{}
\tablelasttail{}
\begin{supertabular}{|m{4.4040003cm}|m{4.642cm}|}
\hline
{\selectlanguage{polish} terminale: } &
\centering\arraybslash{\selectlanguage{polish} \{a,b,c,d\}}\\\hline
{\selectlanguage{polish} funkcje:} &
\centering\arraybslash{\selectlanguage{polish} \{I,N,A,O\}}\\\hline
{\selectlanguage{polish} genów na chromosom:} &
\centering\arraybslash{\selectlanguage{polish} 3}\\\hline
{\selectlanguage{polish} h:} &
\centering\arraybslash{\selectlanguage{polish} 4}\\\hline
{\selectlanguage{polish} generacji:} &
\centering\arraybslash{\selectlanguage{polish} 10}\\\hline
{\selectlanguage{polish} populacja:} &
\centering\arraybslash{\selectlanguage{polish} 30os}\\\hline
{\selectlanguage{polish} mutacja:} &
\centering\arraybslash{\selectlanguage{polish} 0.1}\\\hline
{\selectlanguage{polish} IST:} &
\centering\arraybslash{\selectlanguage{polish} 0.1}\\\hline
{\selectlanguage{polish} RIST:} &
\centering\arraybslash{\selectlanguage{polish} 0.1}\\\hline
{\selectlanguage{polish} GT:} &
\centering\arraybslash{\selectlanguage{polish} 0.1}\\\hline
{\selectlanguage{polish} 1PR:} &
\centering\arraybslash{\selectlanguage{polish} 0.2}\\\hline
{\selectlanguage{polish} 2PR:} &
\centering\arraybslash{\selectlanguage{polish} 0.5}\\\hline
{\selectlanguage{polish} GR:} &
\centering\arraybslash{\selectlanguage{polish} 0.1}\\\hline
\end{supertabular}
\end{center}

\bigskip

Osobnik o najwyższej mierze dostosowania został odnaleziony w siódmej populacji, i choć wartość fitness była względnie wysoka (równa 0.633733), nadal daleka od maksimum. Rozwiązanie zakodowane zostało w chromosomie :

:

gen 1.: \ \ d{\textless}5a!4Id!15c=40b{\textless}3d{\textless}6c{\textless}19b{\textless}0c{\textgreater}23a=26a{\textgreater}25b!10

gen 2.:\ \ c=31b{\textgreater}16Ob=18a=29d{\textgreater}3b!17b{\textgreater}17b{\textgreater}11c!40d{\textgreater}9d=3a=5

gen 3.:\ \ Ac{\textgreater}9OAa!24b!13b{\textless}2c!24c{\textless}17b=0a!13d{\textgreater}18b!21


\bigskip

Otwarte ramki odczytu zostały oznaczone podkreśleniem. Jak zostało wspomniane, wartości liczbowe zawarte w chromosomie odpowiadają identyfikatorowi w tablicy możliwych (tzn występujących w danych treningowych) wartości parametru, do którego są przyrównywane. W tym przypadku, rozpatrywane były wszystkie cztery sparametryzowane cechy badanych kwiatów. Niech \ tablica przedstawiona będzie w postaci \ c[i]=d, gdzie c należy do zbioru termów, i jest kluczem tablicy, d stanowi wartość parametru z danych uczących. Przy tym zestawie treningowym i tym konkretnym chromosomie, wykorzystujemy:

a[24]=5,6

b[2]=3,2

b[13]=4,1

c[9]=4,7

c[31]=5,8

d[5]=0,6


\bigskip

Fenotypem osobnika jest więc zestaw trzech reguł:


\bigskip

Jeśli (d {\textgreater} 0,6cm), to Iris setosa

Jeśli (c ${\neq}$ 4,1cm), to Iris versicolor 

Jeśli (c {\textgreater} 4,7cm) i ((b ${\neq}$ 4,1cm i b {\textless} 3,2cm) lub (a ${\neq}$ 5,6cm)), to Iris virginica.


\bigskip

Co ciekawe, mimo iż długość głowy została ustawiona na 4, co daje całkowitą długość genu równą 13, dwie z trzech reguł składowych zawierały się w jednym terminalu. Mimo to, reguły te prawidłowo oznaczyły niemal wszystkie przypadki należące do klas pierwszej i trzeciej jako należące właśnie do nich i tylko do nich. Zdecydowanie gorzej poradziły sobie z gatunkiem Iris versicolor, gdzie żaden zestaw treningowy nie został prawidłowo oznaczony. Wskaźniki czułości oraz swoistości wyniosły odpowiednio: 0,97 (klasyfikacja negatywna niemal stuprocentowo skuteczna) i 0.653333 (niewiele ponad dwie trzecie zostało poprawnie oznaczone jako należące do danej klasy).


\bigskip

Zachowanie funkcji fitness w tym eksperymencie prezentuje wykres 4.



\begin{figure}
\centering
\begin{minipage}{14.811cm}

\bigskip

Wykres \stepcounter{Wykres}{\theWykres}: Zmiany wartości najlepszej oraz średniej wartości fitness dla przykładu klasyfikacji irysów.
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img039.svm}
\end{minipage}
\end{figure}

\bigskip


\bigskip


\bigskip

\section[Implementacja]{\selectlanguage{polish} Implementacja}

\bigskip

Program stworzony na potrzeby tej pracy, napisany został w języku C++. Wszelkie dane wejściowe przekazywane są w pliku, zawierającym informacje jakiego typu jest rozpatrywany problem, jakie symbole funkcyjne i terminalne mają zostać użyte, parametry oraz dane uczące. Dane te przekazywane są do obiektu klasy Box, który następnie przekazywany jest do pozostałych klas. Dodatkowo, oprócz obiektów pojawiający się w opisie teoretycznym algorytmu, pojawiają się klasy odpowiadające za konstrukcję drzewa oraz wykonywanie programów-fenotypów: klasa \ (de facto wirtualna) ExpressionNode oraz dziedziczące po niej klasy zależne od rozpatrywanego zadania. Te z kolei stanowią klasy nadrzędne dla reprezentantów wierzchołków drzewa – XXOperNode (operatory) oraz XXVarNode (terminale, liście), gdzie XX są przedrostkiem właściwym dla problemu. W założeniu podejście takie ma dawać możliwość rozbudowy aplikacji. 

Rozbieżności \ w działaniu w zależności od problemu występują w trzech miejscach:

\begin{itemize}
\item losowaniu terminali: wynikłe ze przyjętego sposobu reprezentacji chromosomu przy klasyfikacji, operacja realizowana przez metodę Box::getRandTerm()\footnote{Zapis należy odczytywać jako [klasa]::[metoda], czyli [metoda] klasy [klasa]}
\item obliczaniu funkcji przystosowania: z racji tego, że fitness obliczana jest dla każdego chromosomu, a różnorodność rozwiązywanych problemów jest trudna do ograniczenia, metoda odpowiadająca za realizację tego problemu została umieszczona klasie Chromosome i rozróżnia wariant obliczania na podstawie parametru problem, umieszczanego w pliku z danymi wejściowymi
\item budowa drzewa parsowania: klasy dziedziczące po ExpressionNode różnią się pomiędzy sobą przede wszystkim typem przechowywanej wartości (w SR-node'ach wartość typu double, w CL-node'ach – bool) oraz arność i działanie operatorów; podobnie jak wyżej, klasa korzenia inicjalizowana jest w zależności od parametru problem
\end{itemize}

\bigskip


\bigskip

Diagram klas (z pewnym uproszczeniem, pominięte zostały metody pomocnicze) znajduje się na rysunku 6\footnote{Na diagramie strzałki z prostym grotem oznaczają składnik klasy o nazwie widniejącej przy strzałce, grot pusty w środku oznacza dziedziczenie, zaś podstawa strzałki oznaczona czarnym czworobokiem symbolizuje składnik-tablicę. Oznaczenia łączą się, tzn grot biały z kreską w środku oznacza zarówno składnik klasy dzieczącej.}. 



\begin{figure}
\centering
\begin{minipage}{17cm}
Rysunek \stepcounter{Drawing}{\theDrawing}: Diagram klas
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img040.jpg}
\end{minipage}
\end{figure}
Jako że spektrum problemów, w których mechanika GEP mogłaby znaleźć zastosowanie jest szerokie, w implementacji skupiłem się na dwóch opisanych powyżej. Jak pokazuje przykład problemu klasyfikacji, w niektórych zastosowaniach konieczne stają się pewne modyfikacje modelu teoretycznego, w tym przypadku reprezentacja liści drzewa parsowania. Z tego też powodu, mimo że chromosomy nadal przechowywane są w postaci tekstowej, wszelkie modyfikacje wykonywane są na wektorach znaków. Nie należy jednak sądzić, że przeczy to poprzedniemu stwierdzeniu, jakoby GEP nie wymagał kontroli spójności. „Oryginalny” GEP nie jest bowiem przystosowany do porównywania wartości liczbowych i zwracaniu wartości logicznych. Zmianę tą można więc raczej uznać za rozszerzenie abstrakcji terminali, niż zubożenie algorytmu przez dodanie warunków modyfikacji.

„Zmiany pokoleniowe” inicjalizowane są klasie Population. Zgodnie z opisem przedstawionym w rozdziale 2., pierwsza populacja wygenerowana zostaje zupełnie losowo (co sygnalizowane jest przekazaniem do konstruktora klasy flagi równej 1). Obliczanie wartości fitness (w tym przeliczanie jej na wartości procentowe) realizuje metoda Population::getFitness(), wyniki której przechowywane są w tablicach jako prywatne składniki. 

Za tworzenie nowej populacji odpowiada metoda Population::makeNew(), zwracająca wskaźnik do kolejnej generacji. Przebieg działania tej funkcji nie odbiega od modelu teoretycznego – na początku kopiowany jest osobnik o najlepszym dostosowaniu, następnie następuje selekcja ruletkowa. Kolejnymi etapami są kolejne modyfikacje genetyczne, których liczba zależna jest od podanych w danych wejściowych parametrów. Wszystkie one stanowią osobne metody, które losują chromosom do modyfikacji, a następnie wywołują właściwą metodę już w klasie Chromosome. Wyjątek stanowią tu operatory krzyżowania, które, jako że działają na dwóch losowych chromosomach, realizowane są w obrębie klasy Population.


\bigskip

\section[Analiza wyników]{\selectlanguage{polish} Analiza wyników}

\bigskip

Do szerszej analizy działania aplikacji użyłem po dwa zestawy danych uczących dla odnajdywania funkcji oraz klasyfikacji. Przedstawione zostaną zależności pomiędzy parametrami algorytmu a jego skutecznością. Postaram się także skonfrontować otrzymane wyniki z tymi opisanymi przez Ferreirę.


\bigskip

\subsection[Szukanie funkcji I]{\selectlanguage{polish} Szukanie funkcji I}

\bigskip

W eksperymencie zamiarem moim było odtworzenie doświadczenia Ferreiry przedstawionego w [2] w rozdziale 6.1. Szukaną funkcją jest szybko rosnąca funkcja wielomianowa

  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img041.svm}
 


\bigskip

Podobnie jak w rozdziale 3., użyte zostały zbiory F=\{+,-,*,/,Q\}, T=\{a\}, jednak tym razem zastosowany został wzór (2) funkcji fitness, który, obliczając błąd względnie, jest mniej czuły na duże amplitudy wartości zwracanych przez programy-osobniki. Algorytm został uruchomiony stokrotnie dla każdego zestawu parametrów spośród umieszczonych w tabeli 4. Za każdym razem algorytm wykonywał 50 iteracji dla populacji liczących 30 osobników. Tabela 5. przedstawia parametry modyfikacji użyte przez algorytm (wartość 0 nawiasach oznacza modyfikacje, którym nie mogły zostać poddane populacje składające się z chromosomów jednogenowych),

Jako miarę sukcesu przyjąłem stosunek

\   [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img042.svm}
 \ \ \ \ \ \ \ \ \ \ \ \ (5)

gdzie bi oznacza przystosowanie najlepszego osobnika i-tego spośród R przebiegów algorytmu, fmax zaś maksymalną możliwą do osiągnięcia wartość przystosowania (dla M=100 i liczby danych treningowych Ct=10, fmax=1000). Przedstawiony poniżej wykres 5. pokazuje zależności pomiędzy długością genu, a procentową miarą sukcesu. 



\begin{figure}
\centering
\begin{minipage}{11.19cm}
Wykres \stepcounter{Wykres}{\theWykres}: zależność miary sukcesu od długości chromosomu
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img043.svm}
\end{minipage}
\end{figure}

\bigskip



\begin{figure}
\centering
\begin{minipage}{11.245cm}
Wykres \stepcounter{Wykres}{\theWykres}: zależność liczby odnalezionych prawidłowych rozwiązań od długości chromosomu
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img044.svm}
\end{minipage}
\end{figure}

\bigskip

Tabela 4

\begin{center}
\tablefirsthead{}
\tablehead{}
\tabletail{}
\tablelasttail{}
\begin{supertabular}{|m{4.1130004cm}|m{3.134cm}|m{3.345cm}|}
\hline
\centering{\selectlanguage{polish} Liczba genów} &
\centering{\selectlanguage{polish} h} &
\centering\arraybslash{\selectlanguage{polish} długość genu }\\\hline
\centering{\selectlanguage{polish} 1} &
\centering{\selectlanguage{polish} 4} &
\centering\arraybslash{\selectlanguage{polish} 9}\\\hline
\centering{\selectlanguage{polish} 1} &
\centering{\selectlanguage{polish} 6} &
\centering\arraybslash{\selectlanguage{polish} 13}\\\hline
\centering{\selectlanguage{polish} 1} &
\centering{\selectlanguage{polish} 10} &
\centering\arraybslash{\selectlanguage{polish} 21}\\\hline
\centering{\selectlanguage{polish} 1} &
\centering{\selectlanguage{polish} 12} &
\centering\arraybslash{\selectlanguage{polish} 25}\\\hline
\centering{\selectlanguage{polish} 2} &
\centering{\selectlanguage{polish} 4} &
\centering\arraybslash{\selectlanguage{polish} 18}\\\hline
\centering{\selectlanguage{polish} 2} &
\centering{\selectlanguage{polish} 6} &
\centering\arraybslash{\selectlanguage{polish} 26}\\\hline
\centering{\selectlanguage{polish} 2} &
\centering{\selectlanguage{polish} 10} &
\centering\arraybslash{\selectlanguage{polish} 42}\\\hline
\centering{\selectlanguage{polish} 2} &
\centering{\selectlanguage{polish} 12} &
\centering\arraybslash{\selectlanguage{polish} 50}\\\hline
\centering{\selectlanguage{polish} 3} &
\centering{\selectlanguage{polish} 4} &
\centering\arraybslash{\selectlanguage{polish} 27}\\\hline
\centering{\selectlanguage{polish} 3} &
\centering{\selectlanguage{polish} 6} &
\centering\arraybslash{\selectlanguage{polish} 39}\\\hline
\centering{\selectlanguage{polish} 3} &
\centering{\selectlanguage{polish} 10} &
\centering\arraybslash{\selectlanguage{polish} 63}\\\hline
\centering{\selectlanguage{polish} 3} &
\centering{\selectlanguage{polish} 12} &
\centering\arraybslash{\selectlanguage{polish} 75}\\\hline
\centering{\selectlanguage{polish} 4} &
\centering{\selectlanguage{polish} 4} &
\centering\arraybslash{\selectlanguage{polish} 36}\\\hline
\centering{\selectlanguage{polish} 4} &
\centering{\selectlanguage{polish} 6} &
\centering\arraybslash{\selectlanguage{polish} 52}\\\hline
\centering{\selectlanguage{polish} 4} &
\centering{\selectlanguage{polish} 10} &
\centering\arraybslash{\selectlanguage{polish} 84}\\\hline
\centering{\selectlanguage{polish} 4} &
\centering{\selectlanguage{polish} 12} &
\centering\arraybslash{\selectlanguage{polish} 100}\\\hline
\end{supertabular}
\end{center}

\bigskip


\bigskip

Tabela 5: parametry modyfikacji dla rozpatrywanego problemu

\begin{center}
\tablefirsthead{}
\tablehead{}
\tabletail{}
\tablelasttail{}
\begin{supertabular}{|m{4.51cm}|m{4.4300003cm}|}
\hline
{\selectlanguage{polish} mutacja} &
\centering\arraybslash{\selectlanguage{polish} 0.3}\\\hline
{\selectlanguage{polish} IST} &
\centering\arraybslash{\selectlanguage{polish} 0.1 (0)}\\\hline
{\selectlanguage{polish} RIST} &
\centering\arraybslash{\selectlanguage{polish} 0.1 (0)}\\\hline
{\selectlanguage{polish} GT} &
\centering\arraybslash{\selectlanguage{polish} 0.1 (0)}\\\hline
{\selectlanguage{polish} 1PR} &
\centering\arraybslash{\selectlanguage{polish} 0.1 }\\\hline
{\selectlanguage{polish} 2PR} &
\centering\arraybslash{\selectlanguage{polish} 0.4 }\\\hline
{\selectlanguage{polish} GR} &
\centering\arraybslash{\selectlanguage{polish} 0.3 (0)}\\\hline
\end{supertabular}
\end{center}

\bigskip

Co ciekawe, mimo iż wykres 5. wskazuje na dużą zbieżność jakości rozwiązań znalezionych przez chromosomy o dużej długości, wykres 6., przedstawiający liczbę znalezionych rozwiązań prawidłowych (tzn o wartości fitness równej fmax=1000) w zależności o długości chromosomu, wykazuje, że najlepsze rezultaty osiągają chromosomy o długości 36 i 39. Wynik ten podobny jest do uzyskanego przez autorkę systemu, opublikowanego w [2] a przedstawionego na wykresie 7. Autorka nie określa w publikacji co rozumie poprzez „success rate”, \ jednak maksima funkcji przedstawionej na wykresie wskazują, że wyniki przez nią uzyskane nie różnią się znacząco od moich. Różnice wynikać mogą z innych parametrów występowania modyfikatorów użytych przeze mnie oraz z różnic w operacjach mutacji i transpozycji zaznaczonych w rozdziale drugim. 

Z analizy wykresów 5 i 6 można wywnioskować jeszcze jedną wartą odnotowania właściwość. Choć przy długich chromosomach średnia wartość przystosowania zachowuje wysoki poziom, wykazując nawet niewielką tendencję do wzrostu, liczba znalezionych poprawnych rozwiązań spada. Oznacza to, że rzadziej występujące osobniki o maksymalnych wartościach dostosowania mimo wszystko średnią zawyżają. Wniosek, że wraz ze wzrostem długości chromosomu zbieżność algorytmu zwiększa się (tzn maleje różnorodności osobników) w późniejszych generacjach, zdają się potwierdzać obserwacje generacji. Jest to zjawisko niepożądane, gdyż hamuje, czy wręcz zatrzymuje, proces ewolucji\footnote{Wierzchoń w [4] przedstawia metody tzw koewolucji, wspomagające ewolucję poprzez regulując jej przebieg poprzez techniki adaptacyjne, jednak w omawianym algorytmie nie mają one zastosowania.}.


\bigskip


\bigskip


\bigskip

\subsection*{\selectlanguage{polish} }
\begin{figure}
\centering
\begin{minipage}{7.408cm}
  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img045.gif}
 Wykres \stepcounter{Wykres}{\theWykres}: stosunek jakości wyników do długości chromosomów wg. Ferreiry
\end{minipage}
\end{figure}
\subsection[Szukanie funkcji II]{\selectlanguage{polish} Szukanie funkcji II}
Jako drugi przykładem zastosowania GEP dla omawianego problemu, wybrana została funkcja   [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img046.svm}
 wykorzystywana przez Ferreirę w [2], jednak w innym kontekście. Autorka użyła jej by zademonstrować . Zbiór funkcji to F=\{+,-,/,*,Q,E,L,,C,S,T\} gdzie E oznacza funkcję eksponencjalną, L jest logarytmem naturalnym, \ T oznacza logarytm przy podstawie równej 10, S – sinus, C -cosinus. Zestaw danych treningowych, składający się, jak wyżej, z par argument-wartość funkcji, przedstawiony jest poniżej:

\ \ a\ \ f(a)

\ \ {}-0.2639725157548009\ \ 3.194980662652764

\ \ 0.0578905532656938\ \ 1.990520017259985

\ \ 0.3340252901096346\ \ 8.396637039972868

\ \ {}-0.2363345775644623\ \ 3.070889769728257

\ \ {}-0.8557443825668047\ \ 5.879467636957033

\ \ {}-0.0194437136332785\ \ {}-0.7753263223284588

\ \ {}-0.1921343881833043\ \ 2.834702257744086

\ \ 0.5293079101246271\ \ 12.21547266421373

\ \ {}-0.007889741187284598\ \ {}-2.498039834186359

\ \ 0.4389698049506311\ \ 10.40717348588088

\ \ {}-0.1075592926980396\ \ 2.094136356459081

\ \ {}-0.2745569943771633\ \ 3.239272780108398

\ \ {}-0.05953332196045281\ \ 1.197012847673475

\ \ 0.3844929939583523\ \ 9.355807691898551

\ \ {}-0.8749230207363339\ \ 6.006424530013026

\ \ {}-0.236546636250546\ \ 3.071897290438372

\ \ {}-0.1678759417045577\ \ 2.674400531309863

\ \ 0.9506821818220914\ \ 22.48196398441491

\ \ 0.9469791595773622\ \ 22.37501611873555

\ \ 0.6393399100595915\ \ 14.5701285332337


\bigskip


\bigskip

W tym przypadku, przy przyjętych parametrach algorytmu, dokładne rozwiązanie nie zostało znalezione. Najlepszy osobnik wygenerowany został w 60. przebiegu i 26. iteracji:


\bigskip

Eqaaaaaaa{\textbar}*aEQaaaaa{\textbar}EEQaaaaaa{\textbar}


\bigskip

  [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img047.svm}
 


\bigskip

Porównanie tego rozwiązania do funkcji szukanej, prezentuje Wykres[]. Mimo iż wizualnie wykresy różnią się od siebie w stopniu dość znacznym, różnice bezwzględne między wartościami obu funkcji są niewielkie. Stąd rozwiązania znalezione w kolejnych przebiegach różnią się od siebie w o wiele mniejszym stopniu, niż w przykładzie powyżej. Najniższa uzyskana wartość wyniosła 1792,91, podczas gdy najwyższa 1866.39 (przy maksimum wynosiło 1900). Zapewne wynik różniłby się, gdyby do wyliczania funkcji przystosowania zastosowany został wzór (.2) z różnicą procentową.



\begin{figure}
\centering
 [Warning: Image ignored] % Unhandled or unsupported graphics:
%\includegraphics{praca-img/praca-img048.png}

\end{figure}

\bigskip

Podobnie jak powyżej, relatywnie najczęściej najlepsze w generacji rozwiązania generowane były w populacji początkowej.


\bigskip

\subsection[Klasyfikacja I]{\selectlanguage{polish} Klasyfikacja I}

\bigskip

W teście tym porównane zostaną wyniki klasyfikacji osiągnięte metodami zaprezentowanymi w rozdziale 3.2. Rozpatrywany problem, diagnostyka raka piersi\footnote{Źródło: \ Dr. William H. Wolberg, University of Wisconsin Hospitals, Madison}, dostarcza zestaw 699 danych treningowych, składających się z dziewięciu parametrów o wartościach 1-10, reprezentujących skatalogowane cechy badanej próbki, oraz dwie klasy: \ nowotwór złośliwy, oznaczony jako 4, bądź łagodny, oznaczony jako 2 (parametr będący identyfikatorem próbki pominięto). Jak zostało tam opisane, technika wykorzystująca „czysty” GEP poradziła sobie z tym zadaniem w sposób co najmniej zadowalający (ponad 97\% poprawnie zaklasyfikowanych próbek). Dla porównania, zaimplementowana przez mnie wersja algorytmu, została uruchomiona sto razy przy pięćdziesięciu generacjach złożonych z sześćdziesięciu osobników. Za dane uczące posłużył pierwsze 499 zestawów, pozostałe 200 zostały potraktowane jako dane testowe. Najlepszy z wygenerowanych zestawów reguł wyewoluował w 44. generacji szóstego przebiegu algorytmu. Poniżej przedstawione zostały zbiory oraz parametry użyte do eksperymentu, oraz osiągnięty genotyp i fenotyp (operator X oznacza XOR, czyli alternatywa wykluczająca) z przypisanymi już wartościami parametrów

\ \ \ \ \ \ Tabela 6.

\begin{center}
\tablefirsthead{}
\tablehead{}
\tabletail{}
\tablelasttail{}
\begin{supertabular}{|m{4.5360003cm}|m{4.3770003cm}|}
\hline
\centering{\selectlanguage{polish} T } &
\centering\arraybslash{\selectlanguage{polish} \{a,b,c,d,e,f,g,h,i\}}\\\hline
\centering{\selectlanguage{polish} F} &
\centering\arraybslash{\selectlanguage{polish} \{I,N,A,O,X\}}\\\hline
\centering{\selectlanguage{polish} liczba genów w chromosomach} &
\centering\arraybslash{\selectlanguage{polish} 2}\\\hline
\centering{\selectlanguage{polish} h} &
\centering\arraybslash{\selectlanguage{polish} : 5}\\\hline
\centering{\selectlanguage{polish} mutacja} &
\centering\arraybslash{\selectlanguage{polish} 0.3}\\\hline
\centering{\selectlanguage{polish} IST} &
\centering\arraybslash{\selectlanguage{polish} 0.2}\\\hline
\centering{\selectlanguage{polish} RIST} &
\centering\arraybslash{\selectlanguage{polish} 0.2}\\\hline
\centering{\selectlanguage{polish} GT} &
\centering\arraybslash{\selectlanguage{polish} 0.2}\\\hline
\centering{\selectlanguage{polish} 1PR} &
\centering\arraybslash{\selectlanguage{polish} 0.1}\\\hline
\centering{\selectlanguage{polish} 2PR} &
\centering\arraybslash{\selectlanguage{polish} 0.3}\\\hline
\centering{\selectlanguage{polish} GR} &
\centering\arraybslash{\selectlanguage{polish} 0.4}\\\hline
\end{supertabular}
\end{center}

\bigskip

AXOf{\textgreater}10e!5g{\textless}3b{\textless}5i{\textgreater}7c{\textless}3d=7h!3e!1c{\textless}7i=8f{\textgreater}2d{\textless}3 {\textbar} Ic=6OIOf{\textgreater}10e!5g!1c=7c{\textgreater}8a{\textgreater}4c!9c{\textgreater}4c!6i{\textless}5g{\textgreater}4


\bigskip

((f{\textgreater}6) XOR (e${\neq}$4)) I ((g{\textless}2) LUB (b{\textless}3)) \ \ \ :\ \ klasa 1


\bigskip

JEŚLI (c=5) TO \ \ \ \ \ \ \ \ \ \ :\ \ klasa 2

\ \ ((c{\textgreater}7) LUB (a{\textgreater}8) LUB (f{\textgreater}6)), 

W PRZECIWNYM WYPADKU

\ \ JEŚLI (e${\neq}$4) TO

\ \ \ \ (g${\neq}$9)

\ \ W PRZECIWNYM WYPADKU

\ \ \ \ (c=6)


\bigskip


\bigskip


\bigskip


\bigskip

Bibliografia:

[1] C. Ferreira, Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence, Angra do Heroismo, Portugal, 2002

[2] C. Ferreira, Gene Expression Programming: A New Adaptive Algorithm for Solving Problems, \ Complex Systems, 13 (2): 87-129, 2001

[3] Ferreira [art2]

[4] S. T. Wierzchoń, Sztuczne systemy immunologiczne, Akademicka Oficyna Wydawnicza EXIT, Warszawa 2001

[5] Wagner R. Weinert and Heitor S. Lopes: GEPCLASS: A Classification Rule Discovery Tool Using Gene Expression Programming 

[6] Lopes, H.S., Coutinho, M.S., Lima, W.C.: An evolutionary approach to simulate cognitive feedback learning in medical domain. In: Sanchez, E. et al. (eds.): Genetic Algorithms and Fuzzy Logic Systems. World Scientific, Singapore (1997) 193-207.
\end{document}
